# ifndef __fvector_H_
# define __fvector_H_

// The class is like std::vector<> but optimized to not occupy additional memory
// if the vector is empty.
template <typename T>
class fvector {
  public:
	typedef T value_type;
	typedef T * iterator;
	typedef const T * const_iterator;

	fvector () : m_pData (NULL) {}
	fvector (size_t _cSize);
	fvector (const fvector & _other);
	fvector (const_iterator _first, const_iterator _last);
	~fvector () {clear ();}

	fvector & operator = (const fvector & _other);

	void swap (fvector & _other) {std::swap (m_pData, _other.m_pData);}

	void clear ();
	void resize (size_t _cSize);
	void reserve (size_t _cSize) {}

	void assign (const_iterator _first, const_iterator _last);

	size_t size () const {return m_pData ? (reinterpret_cast<const size_t *> (m_pData)) [-1] : 0;}
	bool empty () const {return size () == 0;}
	size_t capacity () const {return size ();}

	iterator       begin ()       {return m_pData;}
	const_iterator begin () const {return m_pData;}
	iterator       end   ()       {return m_pData ? m_pData + size () : NULL;}
	const_iterator end   () const {return m_pData ? m_pData + size () : NULL;}

	const T & operator [] (size_t _cIndex) const {assert (_cIndex < size ()); return m_pData [_cIndex];}
	      T & operator [] (size_t _cIndex)       {assert (_cIndex < size ()); return m_pData [_cIndex];}

	void push_back (const T & _value);
	void pop_back ();

	const T & back () const {return end () [- 1];}
	      T & back ()       {return end () [- 1];}

	const T & front () const {return begin () [0];}
	      T & front ()       {return begin () [0];}

	void insert (iterator _i, const T & _value);
	void insert (iterator _i, const_iterator _begin, const_iterator _end);
	void erase  (iterator _i);

	bool operator == (const fvector<T> & _other) const;

  private:
	T * m_pData;

	static T * _Allocate (size_t _cSize);
	static char * _AddressOf (T * _pData, size_t _cIndex) {return reinterpret_cast<char *> (_pData + _cIndex);}
};

template <typename T>
T * fvector<T>::_Allocate (size_t _cSize) {
	char * const pData = new char [sizeof (size_t) + _cSize*sizeof (T)];
	* reinterpret_cast<size_t *> (pData) = _cSize;
	return reinterpret_cast<T *> (pData + sizeof (size_t));
}

template <typename T>
fvector<T>::fvector (size_t _cSize) {
	if (_cSize == 0)
		m_pData = NULL;
	else {
		// Allocate memory.
		m_pData = _Allocate (_cSize);

		// Initialize elements with default constructor.
		for (size_t c = 0; c < _cSize; ++ c)
			new (_AddressOf (m_pData, c)) T;
	}
}

template <typename T>
fvector<T>::fvector (const fvector & _other) {
	const size_t cSize = _other.size ();
	if (cSize == 0)
		m_pData = NULL;
	else {
		// Allocate memory.
		m_pData = _Allocate (cSize);

		// Copy elements.
		for (size_t c = 0; c < cSize; ++ c)
			new (_AddressOf (m_pData, c)) T (_other.m_pData [c]);
	}
}

template <typename T>
fvector<T>::fvector (const_iterator _first, const_iterator _last) {
	const size_t cSize = _last - _first;
	if (cSize == 0)
		m_pData = NULL;
	else {
		// Allocate memory.
		m_pData = _Allocate (cSize);

		// Copy elements.
		for (size_t c = 0; c < cSize; ++ c)
			new (_AddressOf (m_pData, c)) T (_first [c]);
	}
}

template <typename T>
fvector<T> & fvector<T>::operator = (const fvector & _other) {
	fvector<T> v2 (_other);
	swap (v2);
	return * this;
}

template <typename T>
void fvector<T>::assign (const_iterator _first, const_iterator _last) {
	fvector<T> v2 (_first, _last);
	swap (v2);
}

template <typename T>
void fvector<T>::clear () {
	if (m_pData == NULL)
		return;

	// Call destructors.
	const size_t cSize = size ();
	for (size_t c = 0; c < cSize; ++ c)
		(m_pData [c]).~T ();

	delete [] (reinterpret_cast<char *> (m_pData) - sizeof (size_t));
	m_pData = NULL;
}

template <typename T>
void fvector<T>::resize (size_t _cSize) {
	const size_t cSize = size ();
	if (_cSize == cSize)
		return;

	// Allocate memory.
	T * const pData = _Allocate (_cSize);

	if (_cSize > cSize) {
		// Copy elements.
		size_t c;
		for (c = 0; c < cSize; ++ c)
			new (_AddressOf (pData, c)) T (m_pData [c]);

		// Initialize the rest.
		for (; c < _cSize; ++ c)
			new (_AddressOf (pData, c)) T;
	} else {
		// Copy elements.
		for (size_t c = 0; c < _cSize; ++ c)
			new (_AddressOf (pData, c)) T (m_pData [c]);
	}
	
	clear ();
	m_pData = pData;
}

template <typename T>
void fvector<T>::push_back (const T & _value) {
	const size_t cSize = size ();
	resize (cSize + 1);
	m_pData [cSize] = _value;
}

template <typename T>
void fvector<T>::pop_back () {
	const size_t cSize = size ();
	resize (cSize - 1);
}

template <typename T>
void fvector<T>::insert (iterator _i, const T & _value) {
	const size_t i = _i - m_pData;
	const size_t cNewSize = size () + 1;
	resize (cNewSize);
	assert (cNewSize == size ());
	if (i != cNewSize - 1)
		::memmove (m_pData + i + 1, m_pData + i, (cNewSize - i - 1)*sizeof (T));
	m_pData [i] = _value;
}

template <typename T>
void fvector<T>::insert (iterator _i, const_iterator _begin, const_iterator _end) {
	// TODO:
	assert (false);
}

template <typename T>
void fvector<T>::erase (iterator _i) {
	const size_t i = _i - m_pData;
	const size_t cSize = size ();
	if (i >= cSize) {
		assert (false);
		return;
	}
	const size_t cNewSize = cSize - 1;

	// Allocate memory.
	T * const pData = _Allocate (cNewSize);

	// Copy elements before the erased one.
	size_t c;
	for (c = 0; c < i; ++ c)
		new (_AddressOf (pData, c)) T (m_pData [c]);

	// Copy elements after the erased one.
	for (; c < cNewSize; ++ c)
		new (_AddressOf (pData, c)) T (m_pData [c + 1]);
	
	clear ();
	m_pData = pData;

}

template <typename T>
bool fvector<T>::operator == (const fvector<T> & _other) const {
	const size_t cSize = size ();
	if (_other.size () != cSize)
		return false;

	for (size_t c = 0; c < cSize ; ++ c)
		if (! (m_pData [c] == _other.m_pData [c]))
			return false;

	return true;
}

# endif // __fvector_H_